\documentclass{beamer}

% for themes, etc.
\mode<presentation>
{ \usetheme{boxes} }

\usepackage{times}  % fonts are up to you
\usepackage{graphicx}

% these will be used later in the title page
\title{
Solving Difficult LR Parsing Conflicts by Postponing Them
}
\author{
Luis Garcia-Forte
and
Casiano~Rodriguez-Leon\\
Universidad de La Laguna
}
\date{CoRTA$^{2010}$ September 09-10, 2010}

% note: do NOT include a \maketitle line; also note that this title
% material goes BEFORE the \begin{document}

% have this if you'd like a recurring outline
\AtBeginSection[]  % "Beamer, do the following at the start of every section"
{
\begin{frame}<beamer> 
\frametitle{Outline} % make a frame titled "Outline"
\tableofcontents[currentsection]  % show TOC and highlight current section
\end{frame}
}

\begin{document}

% this prints title, author etc. info from above
\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\frametitle{Outline} % make a frame titled "Outline"
\tableofcontents  % show TOC and highlight current section
\end{frame}

\section{Introduction}

\begin{frame}
\frametitle{Yacc Limitations}

\begin{itemize}
\item
Yacc-like LR parser generators  provide ways to solve shift-reduce mechanisms
based on token precedence. 

\pause \item
No mechanisms are provided for the resolution
of reduce-reduce conflicts or difficult shift-reduce conflicts. 

\pause \item

To solve such kind of conflicts the language designer 
has to modify the grammar. 
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Postponed Conflict Resolution Approach}

\begin{itemize}
\pause \item
The strategy presented here 
extends yacc conflict resolution mechanisms
with new ones, supplying ways to resolve conflicts
that can not be solved using static precedences. 
\pause \item
The algorithm for the generation of the LR tables remains unchanged,
but the programmer can modify the parsing tables
during run time. 
\end{itemize}

\end{frame}

\begin{frame}[fragile]
\frametitle{PPCR Approach: Identify  the Conflict}

\begin{itemize}
\pause \item 
Identify the conflict: What LR(0)-items/productions and tokens are involved?.

\pause \item 
Tools must support that stage, as for example via  the \verb|.output| file generated by \verb|eyapp|.

\pause \item
Suppose  we identify that the participants are the two LR(0)-items 

\begin{itemize}
\pause \item 
$A \rightarrow \alpha_\uparrow$
\pause \item[]
and
\pause \item 
$B \rightarrow \beta_\uparrow$ 
\pause \item[]
when the lookahead token is 
\pause \item[]
\verb|@|.
\end{itemize}
\end{itemize}


\end{frame}

\begin{frame}[fragile]
\frametitle{PPCR Approach: Identify the Conflict}

\begin{itemize}
\pause \item The software must allow the use of symbolic labels to refer
by name to the productions involved in the conflict.

\pause \item
In \verb|Eyapp| names and labels can be 
explicitly given using the directive {\color{blue} \verb|%name|}, using a syntax similar to this one:

\begin{color}{blue}
\begin{eqnarray*}
\mbox{{\tt \%name :rA}}& A &\rightarrow \alpha\\
\mbox{{\tt \%name :rB}}& B &\rightarrow \beta 
\end{eqnarray*}
\end{color}
\end{itemize}
\end{frame}


\begin{frame}[fragile]
\frametitle{PPCR Approach: Identify the Conflict}

\begin{itemize}
\pause \item
Give a symbolic name to the conflict. In this case we choose \verb|isAorB|
as name of the conflict. 

\pause \item
\label{item:mark}
Inside the {\it body} section of the grammar, mark the points of conflict using the 
new reserved word {\color{blue} \verb|%PREC|} followed by the conflict name:

\begin{eqnarray*}
\mbox{{\tt \%name :rA\ }}    A &\rightarrow \alpha &\mbox{\color{blue}\tt\ \%PREC IsAorB }\\
\mbox{{\tt \%name :rA\ }}    B &\rightarrow \beta  &\mbox{\color{blue}\tt\ \%PREC IsAorB }
\end{eqnarray*}
\end{itemize}


\end{frame}


\begin{frame}[fragile]
\frametitle{Conflict Identification: Shift-Reduce Conflicts}
The procedure is similar for shift-reduce conflicts. 
\begin{itemize}
\pause \item
Let us assume we have
identified a shift-reduce conflict between LR-(0) items
\begin{itemize}
\pause \item
$A \rightarrow \alpha_\uparrow$ 
\pause \item[] and 
\pause \item $B \rightarrow \beta\ _\uparrow\ \gamma$ 
\pause for some token \verb|'@'|.  
\end{itemize}

\pause \item  Again, we must give a symbolic name to  $A \rightarrow \alpha$
and mark with the new {\color{blue} \verb|%PREC|} directive 
the places where the conflict occurs:

\begin{eqnarray*}
    \mbox{{\tt \%name :rA\ }}    A &\rightarrow \alpha &\mbox{\color{blue}\tt\ \%PREC IsAorB }\\
    B &\rightarrow \beta  &\mbox{\color{blue}\tt\ \%PREC IsAorB\ \ } \gamma
\end{eqnarray*}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{PPCR Approach: The Conflict Handler}
\begin{itemize}
\pause \item
\label{item:handler}
Introduce a {\color{blue} \verb|%conflict|} directive inside the {\it head} section of
the translation scheme to specify the way the conflict will be solved.

\pause  \item
The directive is followed by some code - known as the {\it conflict handler} -
whose mission is to modify 
the parsing tables. 

\pause \item
This code will be executed
each time the associated conflict state is reached.
\end{itemize}
\end{frame}


\begin{frame}[fragile]
\frametitle{PPCR Approach: The Conflict Handler}
\begin{itemize}
\pause  \item
This is the usual layout of the conflict handler for a reduce-reduce conflict:

\begin{color}{blue}
\begin{verbatim}
%conflict  IsAorB {
  if (is_A) { 
    $self->YYSetReduce('@', ':rA' ); 
  } 
  else { 
    $self->YYSetReduce('@', ':rB' ); 
  }
}
\end{verbatim}
\end{color}
\pause \item

Inside a conflict code handler the Perl default variable \verb|$_| refers to
the input and \verb|$self| refers to the parser object.

\end{itemize}
\end{frame}


\begin{frame}[fragile]
\frametitle{PPCR Approach: The Conflict Handler}
\begin{itemize}
 \item
This is the usual layout of the conflict handler for a shift-reduce conflict:

\begin{color}{blue}
\begin{verbatim}
%conflict  IsAorB {
  if (is_A) { 
    $self->YYSetReduce('@', ':rA' ); 
  }
  else { 
    $self->YYSetShift('@'); 
  }
}
\end{verbatim}
\end{color}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{PPCR Approach: The Conflict Handler}
\begin{itemize}
\pause \item
The method \verb|YYSetReduce| receives a list of tokens 
and a production label, like \verb|:rA|. The call
\begin{color}{blue}
\begin{center}
\begin{tabular}{p{8cm}}
\begin{verbatim}
 $self->YYSetReduce('@', ':rA' )
\end{verbatim}
\end{tabular}
\end{center}
\end{color}
sets the parsing action
for the state associated with the 
conflict \verb|IsAorB| to 
reduce by the production \verb|:rA| when the current lookahead is
\verb|@|.

\pause \item
The method \verb|YYSetShift| receives a token (or a reference to a list of tokens).
The call
\begin{center}
\begin{tabular}{p{8cm}}
\begin{color}{blue}
\begin{verbatim}
 $self->YYSetShift('@')
\end{verbatim}
\end{color}
\end{tabular}
\end{center}
sets the parsing action
for the state associated with the 
conflict \verb|IsAorB| to 
shift when the current lookahead is
\verb|@|.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{PPCR Approach: The Conflict Handler}
\begin{itemize}
\item
\begin{color}{blue}
\begin{verbatim}
%conflict  IsAorB {
  if (is_A) { $self->YYSetReduce('@', ':rA' ); 
  } 
  else { $self->YYSetReduce('@', ':rB' ); }
}
\end{verbatim}
\end{color}
\item
The call to { \color{blue} \verb|is_A| }
represents the context-dependent
dynamic knowledge that allows us to take the right
decision.
\pause \item
It is usually a call to a {\color{blue} nested parser} to check that 
$A \rightarrow \alpha$ applies
but it can also be any other contextual information we have 
to determine which one is the 
right production.
\end{itemize}
\end{frame}


\section{Context Dependent Parsing}

\begin{frame}[fragile]
\frametitle{A Simple Example: Context Dependant Associativity}

\begin{center}
\begin{tabular}{p{8cm}}
\begin{verbatim}
$ cat input_for_dynamicgrammar.txt 
2-1-1 # left:  0 = (2-1)-1
\end{verbatim}
\pause
\begin{verbatim}
RIGHT
\end{verbatim}
\pause
\begin{verbatim}
2-1-1 # right: 2 = 2-(1-1)
\end{verbatim}
\pause
\begin{verbatim}
LEFT
\end{verbatim}
\pause
\begin{verbatim}
3-1-1 # left:  1 = (3-1)-1
\end{verbatim}
\pause
\begin{verbatim}
RIGHT
3-1-1 # right: 3 = 3-(1-1)
\end{verbatim}
\end{tabular}
\end{center}
\end{frame}

\begin{frame}[fragile]
\frametitle{A Simple Example: Body}
\begin{verbatim}
p:    c *   {} 
; 
\end{verbatim}
\pause
\begin{verbatim}
c:    $expr { print "$expr\n" } 
    | RIGHT { $reduce = 0} 
    | LEFT  { $reduce = 1}
;
\end{verbatim}
\pause
\begin{verbatim}
expr: '(' $expr ')'  { $expr } 
    | NUM
\end{verbatim}
\pause
\begin{color}{blue}
\begin{verbatim}
    | %name :M
      expr.left      %PREC leftORright 
      '-' expr.right %PREC leftORright
            { $left - $right }
\end{verbatim}
\end{color}
\pause
\begin{verbatim}
;
%%
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
\frametitle{A Simple Example: Head Section}
\begin{verbatim}
$ cat dynamicgrammar.eyp 
\end{verbatim}
\pause
\begin{verbatim}
%{
my $reduce = 1;
%}
\end{verbatim}
\pause
\begin{color}{red}
\begin{verbatim}
%whites /(\s*(?:#.*)?\s*)/
%token NUM = /(\d+)/
\end{verbatim}
\end{color}
\pause
\begin{color}{blue}
\begin{verbatim}
%conflict leftORright {
  if ($reduce) { $self->YYSetReduce('-', ':M') } 
  else { $self->YYSetShift('-') }
}
\end{verbatim}
\end{color}
\pause
\begin{verbatim}
%expect 1

%%
\end{verbatim}
\end{frame}

\section{Nested Parsing}


\begin{frame}[fragile]
\frametitle{Enumerated and Subrange Types in Pascal}

\begin{itemize}
\item
The problem is taken from the Bison manual.

\begin{verbatim}
type subrange = lo .. hi;
type enum = (a, b, c);
\end{verbatim}

\pause
\item
The Pascal standard allows only numeric literals and constant
identifiers for the subrange bounds (‘\verb|lo|’ and ‘\verb|hi|’), but Extended
Pascal and many other implementations allow
arbitrary expressions there. 

\pause

\begin{verbatim}
type subrange = (a) .. b;
type enum = (a);
\end{verbatim} 

\pause
\item
To aggravate the conflict we have added the C {\it comma} operator
to the language

\begin{verbatim}
type subrange = (a, b, c) .. (d, e);
type enum = (a, b, c);
\end{verbatim}
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Enumerated vs Range: Full Grammar}
\begin{verbatim}
%token ID  = /([A-Za-z]\w*)/
%token NUM = /(\d+)/
\end{verbatim}
\pause
\begin{verbatim}
%left   ','
%left   '-' '+'
%left   '*' '/'
\end{verbatim}
\pause
\begin{verbatim}
%%
type_decl : 'TYPE' ID '=' type ';' ;
\end{verbatim}
\pause
\begin{verbatim}
type : '(' id_list ')' | expr '..' expr ;
\end{verbatim}
\pause
\begin{verbatim}
id_list : ID           | id_list ',' ID ; 
expr :  ID            
     |  NUM            | '(' expr ')'        
     |  expr ',' expr     /* new */
     |  expr '+' expr  |  expr '-' expr
     |  expr '*' expr  |  expr '/' expr
;
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
\frametitle{Identifying the Conflict}
\begin{verbatim}
$ eyapp -v pascalenumeratedvsrange.eyp 
2 reduce/reduce conflicts
\end{verbatim}
\pause
\begin{color}{blue}
\begin{verbatim}
State 11:
    id_list -> ID . (Rule 4)
    expr -> ID .    (Rule 12)
\end{verbatim}
\end{color}
\begin{color}{red}
\begin{verbatim}
    ')' [reduce using rule 12 (expr)]
    ')' reduce using rule 4 (id_list)
    ',' [reduce using rule 12 (expr)]
    ',' reduce using rule 4 (id_list)
\end{verbatim}
\end{color}
\begin{verbatim}

    '*' reduce using rule 12 (expr)
    '+' reduce using rule 12 (expr)
    '-' reduce using rule 12 (expr)
    '/' reduce using rule 12 (expr)
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
\frametitle{Enumerated vs Range: Body}
\begin{verbatim}
type_decl : 'type' ID '=' type ';' ;
\end{verbatim}
\pause
\verb#type : #\\
\verb#      %name ENUM#\\
{\color{blue}
\verb#      Lookahead# 
}
\verb#'(' id_list ')'#\\
\verb#    | %name RANGE#\\
{\color{blue}
\verb#      Lookahead# 
}
\verb#expr '..' expr#\\
\verb#;#\\
\pause
\vspace{-0.5cm}
\begin{color}{blue}
\begin{verbatim}
Lookahead: /* empty */  
  { $is_range = $_[0]->YYPreParse('Range'); }
;
\end{verbatim}
\end{color}
\end{frame}

\begin{frame}[fragile]
\frametitle{Nested Parsing: Future Work}

\begin{verbatim}
$ cat Range2.eyp 
\end{verbatim}
\begin{color}{blue}
\begin{verbatim}
%from pascalnestedeyapp2 import expr
%%
range: expr '..' expr ';'
;
%%
\end{verbatim}
\end{color}
\end{frame}

\begin{frame}[fragile]
\frametitle{Nested Parsing: Current  State}
\begin{verbatim}
$ cat Range.eyp 
%token ID  = /([A-Za-z]\w*)/
%token NUM = /(\d+)/

%left   ','
%left   '-' '+'
%left   '*' '/'

%%
range: expr '..' expr ';'
;

expr : '(' expr ')'   
    | expr '+' expr | expr '-' expr
    | expr '*' expr | expr '/' expr
    | expr ',' expr | ID | NUM
;
%%
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
\frametitle{Enumerated vs Range: Body}
\pause
\verb#id_list : #\\
{\color{blue}
\verb#      %name ID:ENUM#\\
\verb#      ID                     %PREC rangeORenum#\\
}
\verb#    | id_list ',' ID#\\
\verb#;#\\
\pause
\verb#expr : '(' expr ')'   { $_[2] } /* bypass */#\\
{\color{blue}
\verb#    | %name ID:RANGE#\\
\verb#      ID                     %PREC rangeORenum#\\
}
\verb#    | %name PLUS     expr '+' expr#\\
\verb#    | %name MINUS    expr '-' expr#\\
\verb#    | %name TIMES    expr '*' expr#\\
\verb#    | %name DIV      expr '/' expr#\\
\verb#    | %name COMMA    expr ',' expr#\\
\verb#    | %name NUM      NUM#\\
\verb#;#\\
\verb##\\
\verb#%%#\\
\verb##\\
\end{frame}


\begin{frame}[fragile]
\frametitle{Enumerated vs Range: Header}

\pause
\begin{color}{blue}
\verb#%{#\\
\verb#  my $is_range = 0;#\\
\verb#%}#\\
\verb#%conflict rangeORenum {#\\
\verb# if ($is_range) #\\
\verb#  { $self->YYSetReduce(#{\color{red} \verb#[',', ')']#}\verb#, 'ID:RANGE' ); }#\\
\verb# else #\\
\verb#  { $self->YYSetReduce(#{\color{red} \verb#[',', ')']#}\verb#, 'ID:ENUM' ); }#\\
\verb#} #\\
\end{color}
\pause
\begin{verbatim}
%token ID  = /([A-Za-z]\w*)/
%token NUM = /(\d+)/
\end{verbatim}
\pause
\begin{verbatim}
%left   ','
%left   '-' '+'
%left   '*' '/'
\end{verbatim}
\pause
\begin{verbatim}
%expect-rr 2
%%
\end{verbatim}
\end{frame}

\begin{frame}[fragile]
\frametitle{Enumerated vs Range: Execution}
\begin{color}{blue}
\begin{verbatim}
$ eyapp -P Range.eyp 
\end{verbatim}
\pause
\begin{verbatim}
$ eyapp -TC pascalnestedeyapp2.eyp 
\end{verbatim}
\pause
\begin{verbatim}
$ ./pascalnestedeyapp2.pm -t -i -m 1 \
               -c 'type e = (x, y, z);'
\end{verbatim}
\end{color}
\pause
\begin{verbatim}
typeDecl_is_type_ID_type(
  TERMINAL[e],
  ENUM(
    idList_is_idList_ID(
      idList_is_idList_ID(ID(TERMINAL[x]), 
                          TERMINAL[y]),
      TERMINAL[z]
    )))
\end{verbatim}
\end{frame}

\section{Conclusions}

\begin{frame}
\frametitle{Conclusions}

\begin{itemize}
\pause \item The new conflict resolution mechanisms provide ways to resolve conflicts
that can not be solved using static precedences.
\pause \item They also provides 
finer control over the conflict resolution process
than existing alternatives, like GLR and backtracking LR.
\pause \item
There are no limitations
to PPCR parsing, since the conflict handler is implemented in a universal language and it then 
can resort to any kind of nested parsing algorithm. 
\pause \item
The conflict resolution mechanisms presented 
here can be introduced in any LR parsing tools.
\pause \item
It certainly involves more programmer work 
than branching methods like GLR or backtracking LR.
\end{itemize}

\end{frame}

\begin{frame}
\begin{center}
\small{
\url{http://parse-eyapp.googlecode.com/svn/branches/PPCR}
}
\vskip4pt
\pause
\huge{Thanks!}
\end{center}
\end{frame}

\end{document}

